package UnionFind;

public class _765_CouplesHoldingHands {
    //native solution
    public int minSwapsCouples_1(int[] row) {
        int count = 0;
        for (int i = 0; i < row.length - 1; i += 2) {
            boolean male = false;
            if (row[i] % 2 == 0) {
                male = true;
            } else {
                male = false;
            }
            if ((male && row[i + 1] == row[i] + 1) || (!male && row[i + 1] == row[i] - 1)) {

            } else {
                for (int j = i + 1; j < row.length; j++) {
                    if (male) {
                        if (row[j] == row[i] + 1) {
                            int temp = row[i + 1];
                            row[i + 1] = row[j];
                            row[j] = temp;
                            count++;
                        }
                    } else {
                        if (row[j] == row[i] - 1) {
                            int temp = row[i + 1];
                            row[i + 1] = row[j];
                            row[j] = temp;
                            count++;
                        }
                    }
                }
            }

        }
        return count;
    }

    //second method:use union-find
    private class UF {
        private int[] parents;
        public int count;
        UF(int n) {
            parents = new int[n];
            for (int i = 0; i < n; i++) {
                parents[i] = i;
            }
            count = n;
        }

        private int find(int i) {
            if (parents[i] == i) {
                return i;
            }
            parents[i] = find(parents[i]);
            return parents[i];
        }

        public void union(int i, int j) {
            int a = find(i);
            int b = find(j);
            if (a != b) {
                parents[a] = b;
                count--;
            }
        }
    }

}
